Titre :
Efficient Enumeration of Conjunctive Queries over X-underbar Structures

Par :
Olivier Gauwin
(Université de Mons, Belgique)

Résumé :
This talk focuses on efficient enumeration algorithms for conjunctive
queries for databases over binary relations that satisfy the X-underbar
property. Tree-like relations such as XPath axes or grids are natural
examples of such relations. Enumeration algorithms amount to output answers
to queries with a small delay between consecutive answers, while allowing
preprocessing the input structure. We first present an algorithm for
conjunctive queries over X-underbar structures, avoiding an exponential
blowup appearing in existing algorithms. Then, we consider acyclic
conjunctive queries and show that such queries admit an enumeration
algorithm with a smaller delay. As an application of our method, we also
show how these algorithms apply to XPath queries evaluation over XML
documents. Finally, we consider conjunctive queries with possible
inequalities between variables, which query evaluation turns out to be NP
hard.